DSC 40B – Theoretical Foundations of Data Science II

Problems tagged with "theoretical lower bounds"

Problem #007

Tags: theoretical lower bounds

Suppose you are given a (possibly unsorted) array containing \(n\) elements. Each element is either zero or one. You are tasked with determining if the majority (at least half) of the array's elements are one.

What is the tight theoretical lower bound for the worst case time complexity of this problem?

Solution

\(\Theta(n)\)

Problem #008

Tags: theoretical lower bounds, sorted structure

Consider the same problem as above, except now you may assume that the array is sorted. What is the tight theoretical lower bound for the worst case time complexity of any algorithm which solves this problem?

Solution

\(\Theta(1)\)

Problem #036

Tags: theoretical lower bounds

Suppose you are given a (possibly unsorted) array of \(n\) floating point numbers and are tasked with counting the number of elements in the array which are within ten of the array's maximum (you are not told the maximum). That is, you must count the number of elements \(x\) such that \(m - x \geq 10\), where \(m\) is the array's maximum. You may assume that the array does not contain duplicate numbers.

What is the tight theoretical lower bound for the worst case time complexity of this problem?

Solution

\(\Theta(n)\).

It takes \(\Theta(n)\) time to find the maximum. After this, we loop through and keep track of how many elements are within ten of the maximum -- this also takes \(\Theta(n)\) time.

Problem #038

Tags: theoretical lower bounds

Suppose you are given a (possibly unsorted) array of \(n\) floating point numbers and are tasked with counting the number of elements in the array which are within ten of the array's maximum (you are not told the maximum). That is, you must count the number of elements \(x\) such that \(m - x \geq 10\), where \(m\) is the array's maximum. You may assume that the array does not contain duplicate numbers.

Now you may assume that the array is sorted.

This question has two parts:

First, give the tight theoretical lower bound for the worst case time complexity of any algorithm which solves this problem:

Solution

\(\Theta(\log n)\)

Second, give a short description of an optimal algorithm. Your description does not need to be exact or very long (3 to 4 sentences will do). You do not need to provide pseudocode, but you can if you wish.

Solution

The maximum \(m\) can be found in \(\Theta(1)\) time -- it is the last element of the array. Use binary search (\(\Theta(\log n)\) time) to look for \(m - 10\), but modify the code so that the last-checked index is returned if \(m - 10\) is not found (everything to the right of that index is at least \(m - 10\)). Subtract this index from \(n\) to find the number of elements within 10 of the maximum.

Problem #063

Tags: theoretical lower bounds

Consider again the problem of determining whether there exists a pair of numbers in an array which, when added together, equal the maximum number in the array. Additionally, assume that the array is sorted.

True or False: \(\Theta(n)\) is a tight theoretical lower bound for this problem.

True False
Solution

True.

Any algorithm must take \(\Omega(n)\) time in the worst case, since in the worst case all elements of the array must be read.

This is tight because there is an algorithm that will compute the answer in worst-case \(\Theta(n)\) time. Namely, this is an instance of the ``movie problem'' from lecture, where instead of finding two numbers which add to an arbitrary target, we're looking for a specific target: the maximum. We saw an algorithm that solved the movie problem in \(\Theta(n)\) time, where \(n\) was the number of movies. Since the maximum is computed in \(\Theta(1)\) time for a sorted array, we can use the same algorithm to solve this in \(\Theta(n)\) time as well.

Problem #065

Tags: theoretical lower bounds, sorted structure

Suppose \(a\) and \(b\) are two numbers, with \(a \leq b\). Consider the problem of counting the number of elements in an array which are between \(a\) and \(b\); that is, the number of elements \(x\) such that \(a \leq x \leq b\). You may assume for simplicity that both \(a\) and \(b\) are in the array, and there are no duplicates.

Part 1)

What is a tight theoretical lower bound for this problem, assuming that the array is unsorted? State your answer in asymptotic notation as a function of the number of elements in the array, \(n\).

Solution

\(\Theta(n)\).

Since the array is in arbitrary order, we have to at least read all of the elements, taking \(\Omega(n)\) time. This is a tight lower bound, because we can count the number of elements between \(a\) and \(b\) by looping through and checking whether each element is in \([a, b]\) in linear time.

Part 2)

What is a tight theoretical lower bound for this problem, assuming that the array is sorted? State your answer in asymptotic notation as a function of the number of elements in the array, \(n\).

Solution

\(\Theta(\log n)\).

We can do this in worst-case \(\Theta(\log n)\) time with binary search: find the index of \(a\) in worst-case \(\Theta(\log n)\) time; find the index of \(b\) in worst-case \(\Theta(\log n)\) time; and subtract the two indices (and add one) to get the total number of elements between \(a\) and \(b\), inclusive.

There cannot be an algorithm that is better than \(\Theta(\log n)\) in the worst case, so this is a tight lower bound. To see why, recognize that we can solve the query problem (determine True/False if a target \(t\) is in a sorted array) with any algorithm that solves this problem by setting \(a = b = t\). If an algorithm solves this problem in faster than \(\Theta(\log n)\), it will also solve the query problem in faster than \(\Theta(\log n)\), but we saw in class that the query problem has a theoretical lower bound of \(\Theta(\log n)\), so such an algorithm cannot exist.

Problem #087

Tags: theoretical lower bounds

Consider the following problem: given a (possibly unsorted) list of size \(n\) containing only ones and zeros, determine if the number of ones is equal to the number of zeros.

Part 1)

What is a tight theoretical lower bound for this problem? State your answer as a function of \(n\) using asymptotic notation.

Solution

\(\Theta(n)\)

Part 2)

Now assume that the input array is guaranteed to have the following structure: there will be \(a\) ones, followed by \(b\) zeros, followed again by \(a\) ones. An example of such an array is: [1, 1, 0, 0, 0, 1, 1]. In this example, \(a = 2\) and \(b = 3\).

Consider the same problem as before: that is, given an array satisfying the above assumption, determine if the number of ones in the array is equal to the number of zeros. Of course, \(a\) and \(b\) are not known ahead of time.

What is a tight theoretical lower bound for this problem?

Solution

\(\Theta(1)\) Let \(n\) be the length of the array. Assume that \(n\) is even (if it is odd, we can immediately say that there are not an equal number of ones and zeros). In fact, we can assume that \(n\) is divisible by four, since \(n = a + b + a = 2a + b\), which must equal \(4a\) if there are an equal number of ones and zeros.

For there to be an equal number of ones as zeros, the middle \(n/2\) elements must be zero, while the first \(n/4\) and last \(n/4\) must be ones. If that is the case, then the last one in the first group of ones will occur at index \(n / 4 - 1\), and the first zero will occur at \(n / 4 \) A constant-time algorithm is to check the element at index \(n/4 - 1\) and verify that it is a one. Then we check the element at index \(n/4 \) and check that it is a zero.

Consider, for example, this array with \(n = 10\):

\[\mintinline{python}{[1, 1, 1, 0, 0, 0, 0, 1, 1, 1]}\]

Then \(n / 10 = 10 / 4 = 2.5 = 2\). Therefore, we check the elements at index 1 and 2 in constant time and find them to both be one, which tells us that this array does not have an equal number of zeros and ones.

Now consider the array below:

\[\mintinline{python}{[1, 1, 0, 0, 0, 0, 1, 1]}\]

Since \(n = 8\), we again check the elements at index 1 and 2. We find 1 and 0, which tells us that the array does have an equal number of zeros and ones, as expected.

Problem #181

Tags: best and worst case, theoretical lower bounds

Consider the following problem: given two sorted lists, A and B, each containing \(n\) numbers, determine if the two lists share an element in common. That is, determine if there is a number \(x\) which appears in both lists.

Part 1)

What is a tight theoretical lower bound for this problem? Again, you may assume that the lists are both sorted. State your answer in asymptotic notation as a function of \(n\).

Part 2)

(2 points) Briefly (in 50 words or less) describe an algorithm for solving this problem and state its worst case time complexity. To earn full credit, you should give the optimal algorithm, but partial credit will be awarded for sub-optimal solutions. You may write pseudocode if you like, but an explanation in words is also sufficient. Make sure that you only state one algorithm!

Solution

Here's an approach that takes \(\Theta(n)\); it's similar to what we did in lecture for the movie problem.

Start with i = j = 0. If A[i] == A[j], return True, since you've found an element in common. If A[i] > A[j], increment j, otherwise increment i. Takes \(\Theta(n)\) time.

The brute force approach also earns credit: Loop over all pairs, checking if A[i] == B[j] for each pair. This takes \(\Theta(n^2)\) time.

Problem #204

Tags: theoretical lower bounds

In this problem, assume that \(A\) and \(B\) are sorted lists, each containing \(n\) numbers.

Part 1)

What is the best possible (worst case) time complexity of any algorithm for finding the smallest difference between a number in \(A\) and a number in \(B\)?

Part 2)

What is the best possible (worst case) time complexity of any algorithm for finding the biggest difference between a number in \(A\) and a number in \(B\)?